import collections
class Treenode:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = 0
        
class Solution(object):
    def deleteDuplicateFolder(self, paths):
        root = Treenode('1')
        for a_path in paths:
            node = root
            for layer in a_path:
                if layer in node.neighbors:
                    node = node.neighbors[layer]
                else:
                    new_node = Treenode(layer)
                    node.neighbors[layer] = new_node
                    node = new_node
        p = collections.defaultdict(set)

        def dfs(node):
            temp_list = []
            count = 0
            for item in node.neighbors.values():
                temp_list.append(dfs(item))
                count += 1
            temp_list.sort()
            next_s = ''.join(temp_list)
            if count > 0:
                p[next_s].add(node)
            now_s = '(' + node.val + next_s + ')'
            return now_s
        dfs(root)
        for nodes in p.values():
            if len(nodes) >= 2:
                for node in nodes:
                    node.flag = 1
        node = root
        
        def dfs2(node):
            pop_dict = set()
            for v, v_node in node.neighbors.items():
                if v_node.flag == 1:
                    pop_dict.add(v)
                else:
                    dfs2(v_node)
            for v in pop_dict:
                node.neighbors.pop(v)
        dfs2(root)

        out = []
        st = []
        def dfs3(node):
            if node.val != '1':
                st.append(node.val)
                out.append(st.copy())
                for v in node.neighbors.values():
                    dfs3(v)
                st.pop()
            else:
                for v in node.neighbors.values():
                    dfs3(v)
        
        dfs3(root)
        out.sort(key = lambda x: len(x))
        return out



        

data = Solution()
# paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
# print(data.deleteDuplicateFolder(paths))
# paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
# print(data.deleteDuplicateFolder(paths))
# paths = [["a","b"],["c","d"],["c"],["a"]]
# print(data.deleteDuplicateFolder(paths))
# paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"]]
# print(data.deleteDuplicateFolder(paths))
# paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"],["b","w"]]
# print(data.deleteDuplicateFolder(paths))
# paths = [["e"],["e","e"],["e","e","b"],["e","e","d"],["b"],["b","c"],["b","b"],["b","b","b"],["c"],["d"],["d","b"],["d","d"],["d","d","c"],["d","d","a"],["d","a"],["d","a","a"],["d","a","a","a"],["a"],["a","a"],["a","a","b"],["a","a","b","e"],["a","c"],["a","c","e"],["a","c","e","a"],["a","c","e","a","d"],["a","c","e","a","d","e"],["a","c","e","e"],["a","c","e","d"],["a","c","d"],["a","c","d","c"],["a","c","d","c","e"],["a","c","d","b"],["a","c","a"],["a","c","a","c"],["a","c","a","e"],["a","c","a","e","a"],["a","c","a","e","b"],["a","c","a","e","e"],["a","c","a","e","e","b"],["a","c","a","a"]]
# print(data.deleteDuplicateFolder(paths))
paths = [["a"],["a","c"],["a","d"],["a","d","e"],["b"],["b","e"],["b","c"],["b","c","d"],["f"],["f","h"],["f","h","i"],["f","j"],["g"],["g","j"],["g","h"],["g","h","i"]]
print(data.deleteDuplicateFolder(paths))